#include <iostream>
#include <iterator>
#include <cstring>
#include <cstdlib>
#include <ctime>

using namespace std;

// problem 2
void rand_permutation(const char* str) {
  if (str) {
    size_t len = strlen(str);
    char* output = new char[len+1];
    strcpy (output, str);

    srand(time(NULL));
    size_t pos = 0;
    while (pos < len-1) {
      size_t r = rand() % (len - pos);
      swap (output[pos], output[pos+r]);
      pos++;
    }

    cout << output << endl;
    delete [] output;
  }
}

// problem 3
void choose_rec(const char* arr, char* output, size_t n, size_t m, size_t in_pos, size_t out_pos);

void choose(const char* arr, size_t n, size_t m) {
  if (n < m) {
    throw "n cannot be smaller than m";
    return;
  }
  
  char* output = new char[m+1];
  memset(output, '\0', m+1);

  choose_rec(arr, output, n, m, 0, 0);
  delete [] output;
}

void choose_rec(const char* arr, char* output, size_t n, size_t m, size_t in_pos, size_t out_pos) {
  if (m == 0) {
    cout << output << endl;
    return;
  }
  if (n == m) {
    memcpy (output+out_pos, arr+in_pos, m);
    cout << output << endl;
    return;
  }

  choose_rec(arr, output, n-1, m, in_pos+1, out_pos);
  output[out_pos] = arr[in_pos];
  choose_rec(arr, output, n-1, m-1, in_pos+1, out_pos+1);
  output[out_pos] = '\0';
}

void rand_choose(const char* arr, size_t n, size_t m) {
  if (n < m) {
    throw "n cannot be smaller than m";
    return;
  }
  
  srand(time(NULL));
  size_t selected = 0;
  size_t pos = 0;
  while (selected < m) {
    double r = rand() * 1.0 / RAND_MAX;
    double threshold = 1.0 * (m - selected) / (n - pos);

    if (r < threshold) {
      cout << arr[pos];
      selected++;
    }
    pos++;
  }
}

// problem 4


int main() {
  cout << "Problem 2: random permutation" << endl;
  rand_permutation("abcdefg");
  cout << endl;

  cout << "Problem 3" << endl;
  cout << "Test combination choose" << endl;
  cout << "ways to choose 3 letters from abcde" << endl;
  choose("abcde", 5, 3);
  cout << "Test randomized choose" << endl;
  rand_choose("abcde", 5, 3);
  cout << endl;

  return 0;
}
